It is well known to obtain three-dimensional arrays of data representing one or more physical properties at regular grid positions within the interior of solid bodies. Such data can be obtained by non-intrusive methods such as computed axial tomographic (CAT) x-ray scanning systems, by nuclear magnetic resonance (NMR) imaging systems, or by other non-intrusive mechanisms such as ultrasound, positron emission tomography (PET), emission computed tomography (ECT) and multimodality imaging (MMI). Each of these techniques produces a planar, grid-like array of values for each of a succession of slices of the solid object, thus providing a three-dimensional array of such values. Typically, the solid object is a human body or a portion thereof, although the method is equally applicable to other natural or artificial bodies. In the case of CAT scanning, the physical value would be the coefficient of x-ray absorption. For NMR imaging, the physical value would be the spin-spin or the spin-lattice relaxation time. In any event, the measured physical values reflect the variations in composition, density or surface characteristics of the underlying physical structures. Such a three-dimensional data array typically consists of a plurality of sets of three-dimensional (x,y,z) coordinates distributed at regular positions in a cubic or parallelepiped lattice within the body, and at least one value (V.sub.xyz) of the physical property being associated with each respective one of the coordinate positions. Each cubically adjacent set of eight such positions defines a cubic volume called a "voxel" with a physical property value being specified for each of the eight voxel vertices. In turn, each voxel "neighborhood" includes the voxel itself and the immediately adjacent six voxels which share a common face; thus, a voxel neighborhood is a cubic volume including seven voxels having 32 physical values associated with the voxel vertices.
It is likewise known to utilize such three-dimensional arrays of interior physical values to generate visual images of the interior structures within the body. In the case of the human body, the visual images thus produced can be used for medical purposes such as diagnostics or for the planning of surgical procedures. In order to display two-dimensional images of such three-dimensional interior structures, however, it is necessary to locate the position of the surface of such structure within the array of physical values. This is accomplished by comparing the array values to a single threshold value, or to a range of threshold values, corresponding to the physical property values associated with that surface. Bones or any other tissue, for example, can be characterized by a known range of density values to which the array values can be compared. Once the surface location is determined, this surface must be shaded so as to give the human eye the correct impression of the shape and disposition of that surface when it is displayed on a two-dimensional display device. To provide such shading, the angular direction of a vector normal or orthogonal to the surface at each point on the surface is compared to the viewing angle of the observer. The intensity of shading can then be adjusted so as to be proportional to the difference between these angles. Such angular difference information can also be used to control the colors incorporated in the displayed images, thus providing yet another visual clue to the surface disposition. Normal vectors with components directed away from the viewing angle can be ignored since the associated surfaces are hidden from view.
One method for approximating the surface of an internal structure is the so-called "marching cubes" method, disclosed in H. E. Cline et al. U.S. Pat. No. 4,710,876, granted Dec. 1, 1987, and assigned to applicants' assignee. In this method, the surface segment intersecting a voxel is approximated by one of a limited number of standardized plane polygonal surfaces intersecting the voxel. One particular standardized surface is selected by a vector representing the binary differences between the threshold value and the eight voxel vertex values. The surface-to-voxel intersection coordinates, as well as the normal vector, for each such standardized polygonal surface set can then be calculated or obtained by table look-up techniques. The final surface is assembled as a mosaic, using all of the standardized polygons as tessera or tiles. Appropriate intensity values derived from the normal vector angles can be displayed immediately for viewing, or stored for later display. H. E. Cline et al. U.S. Pat. No. 4,729,098, granted Mar. 1, 1988, and also assigned to applicants' assignee, shows a variation of the marching cubes method using nonlinear interpolation to locate more accurately the coordinates of the tessellated standardized polygons.
Another method for approximating the surface of an internal structure is the so-called "dividing cubes" method, disclosed in H. E. Cline et al. U.S. Pat. No. 4,719,585, granted Jan. 12, 1988, and also assigned to applicants' assignee. In this method, the values at the vertices of the voxel are used to interpolate, in three dimensions, values at regularly positioned intra-voxel sub-grid locations. These interpolated sub-grid values can then be used to locate the surface position more precisely and to calculate the normal vector more accurately. The present invention is an extension of, and improvement on, the dividing cubes method of approximating surface locations and surface normals.
In order to distinguish between different internal structures with the same or similar physical property values, W. E. Lorensen et al. U.S. Pat. No. 4,751,643, granted Jun. 14, 1988, and likewise assigned to applicants' assignee, discloses a technique for labeling surfaces with similar property values and using adjacency criteria with respect to a "seed" location in the particular structure of interest to segregate the desired surface from all of the labeled surfaces. The copending application of H. E. Cline et al., Ser. No. 907,333, filed Sept. 15, 1986, also assigned to applicants' assignee, discloses another technique of segregating similar structures by determining connectivity from adjacent information. Copending application Ser. No. 943,357, filed Dec. 19, 1986, for H. E. Cline et al., also assigned to applicants' assignee, discloses yet another technique for differentiating internal structures in which a linear pass is made through the data array to locate and label all of the different structures along the scan line by counting structure interfaces.
Thus it is known to use a single array of values of a physical property within the interior of a solid body to generate perspective images of arbitrarily selected internal structures within the body, seen as if viewed from arbitrarily chosen viewing angles, all by manipulating the selfsame single array of values. Unfortunately, the amount of processing necessary to produce a single image in this way is so large that it has heretofore been difficult to produce images fast enough to keep pace with many ongoing procedures. Moreover, the need for real time, interactive generation of such images to support ongoing medical or surgical procedures is increasing as the complexity and delicacy of surgical procedures has increased in the recent past. Organ transplants, heart bypass surgery and cosmetic surgery have all increased in complexity and precision as the boundaries of medical knowledge have expanded. There is therefore a growing need for large numbers of real time three-dimensional images, generated as needed in the course of ongoing surgery.
Accordingly, one object of the invention is to provide a method of, and apparatus for, generating real time, two-dimensional perspective images of structures within a three-dimensional body, seen as if viewed from arbitrarily chosen viewing angles.
Another object of the invention is to provide a highly parallel, pipelined processor capable of generating, at a relatively rapid rate, images of internal structures of a three-dimensional body.
Another object of the invention is to provide a method and apparatus for interactively generating real time, two-dimensional perspective images of three-dimensional structures within a body.